<HTML>
<HEAD>
<TITLE>CS 440 Program 3</TITLE>
</HEAD>

<font size = 4>
<body bgcolor = "ffffff">

<CENTER><H2>CS 440
<BR>Program 3</H2></CENTER>

<H3><CENTER>due
<BR>October 28, 2011</CENTER></H3>

<H3>The Program</H3>

In this program you will add a bison-based parser, symbol table
access, and some code generation to your compiler.  This is the
largest of the pieces of your compiler.

<P>The parser is built around the grammar in the <A href =
"paxi.html">PAXI Language Definition</A>.
An ASCII file containing just the grammar can be found <A
href="paxi-bnf.txt">here</A>.  Use your
favorite text editor to convert this into the basis for your bison
file.

<H3>The Parser</H3>

The parser is straight forward. You will need a <EM>%union</EM>
declaration, however, with three field types -- one for
<EM>integer</EM>, one for <EM>pointer to character</EM>, and one for
<EM>pointer to symbol table entry</EM>. (The pointer to character type
will be used to get ID strings from the scanner.)

<P>You will have to make a few small additions to your flex file.
Pass integer values (from the action for NUMBER) and strings (from the
action for ID) to the parser through assignment to <EM>yylval</EM>.

<P>Most of the effort in building the bison file will be in accessing
the symbol table and in code generation.

<H3>Calling the Symbol Table Routines</H3>

Your program will call the <EM>insert</EM> function from your symbol
table to create new table entries whenever a declaration is parsed and
will call the <EM>lookup</EM> function whenever an identifier is
referenced.

<H3>New Table Entries</H3>

A new table entry will be made in each of four situations: a global
declaration, a procedure definition, a procedure parameter being read,
and a local declaration.

<P>Global <EM>scalar variables</EM> are declared in each right hand
side of production 5, &lt;global_var_list&gt;.  A character string
(for the <EM>name</EM> field) should be attached to each ID token.
The <EM>size</EM> field will be 1.  <EM>Arrays</EM> are declared in
production 8, &lt;single_array&gt;.  The <EM>name</EM> field will be
attached to the ID token and the <EM>size</EM> field will be attached
to the NUMBER token.

<P>To find a <EM>location</EM> field value for globals you must
<EM>allocate</EM> memory in the data store for the item (variable or array) and
<EM>bind</EM> the item to the memory allocated to it. This is done by keeping a
"next available" counter with the address (data store index) of the next place
which is available to be allocated. This counter is increased by the size of the
item (<EM>allocating</EM>). The value of the counter before allocating becomes
the location field (<EM>binding</EM>). This counter is initially 510.

<P><EM>Procedures</EM> are declared in production 10,
&lt;procedure_decl&gt;.  Again, the <EM>name</EM> field will be
attached to the ID token.  The <EM>size</EM> field will hold the
number of formal parameters.  These must be <EM>counted</EM> from the
number of entries in the parameter list.  This can be done in
production 12, &lt;formal_list&gt;, by incrementing a counter.

<P>When a symbol table entry is made for a parameter or a local
variable you must make sure that it can be distinguished from a
possible global variable of the same name.  The easiest way to do this
is by <EM>mangling</EM> the name.  Append the name of the procedure it
is declared in to the ID, separated by a character which cannot appear
in an identifier (e.g. '#' or '@').

<P><EM>Parameters</EM> are declared in production 12,
&lt;formal_list&gt;.  The <EM>name</EM> field is built from the string
attached to the ID token.  The <EM>size</EM> is 1.  The
<EM>location</EM> field is the number (starting with 1 in each
procedure) of the parameter in the parameter list.  This is computed
from the counter incremented in this production.

<P><EM>Local variables</EM> are declared in (each right hand side of)
production 15, &lt;local_var_list&gt;.  The <EM>name</EM> field is
built from the string attached to ID and <EM>size</EM> is 1.  The
<EM>location</EM> field is the number (starting with 1 in each
procedure) of the local variable.  As with parameters, this is found
by keeping a counter and incrementing it as each local variable is
declared.

<H3>Looking Up Table Entries</H3>

Anywhere in a program where and identifier is used <EM>other than
where it is being defined</EM> it must be looked up in the symbol
table.  In these places a semantic check must be made (to make sure,
for example, that a procedure name is not being used as a variable)
and the <EM>location</EM> field must be made available for code
generation.

<P>Scalar variables, arrays, parameters, and/or local variables are
referenced in productions 30 (&lt;variable&gt;), 31
(&lt;read_statement&gt;), and 32 (&lt;write_statement&gt;).
Procedures are referenced in production 25 (&lt;call&gt;).  When an ID
is found where a variable is expected you must first check to see if a
local variable exists with that name.  If none does, check for a
global variable.

<H3>Code Generation</H3>

For Program 3 you will do code generation for variable and array
references, arithmetic, the read and write statements, and the
assignment statement.

<P>Code generation is done by keeping a copy of the code store array
in the compiler and, from appropriate productions in the parser,
writing instructions into this array.

<P>All arithmetic will be done using the stack.  That is, a binary
operation will pop two arguments from the stack into a temporary
location (500 - 509 in the data store), perform the operation, and
push the result.

<P>Details on code generation will be discussed in class.

<H3>To Hand In</H3>

As usual you will hand in your source code and a terminal session using 
sample data to be provided later.

</HTML>
